1. Field of the Invention
This invention relates to channel allocation in cellular telephony, and in particular to a method for dynamically allocating channels to cells according to demand.
2. Related Art
A cellular telephone network consists of a number of fixed base station transceivers and a much larger number of mobile handsets which communicate with base stations via a radio channel. The number of radio channels which the operator is permitted to use is limited, and there are not enough for each phone call in the network to be carried on a different channel. Thus a central principle of such networks is channel reuse (Lee, W. C. Y.: Mobile Cellular Telecommunications Systems. McGraw-Hill Book Company, New York, 1989): at any time many base stations may be transceiving on each channel. This introduces the possibility of interference between phone calls. Interference from other calls using the same channel is known as xe2x80x98co-channel interferencexe2x80x99. xe2x80x98Adjacent channelxe2x80x99 interference, due to another call using a different channel, is also a problem: a call made on a channel corresponding to a frequency band of 4000-4025 kHz is liable to interference from a call on the adjacent band; 4025-4050 kHz. Adjacent channel interference can occur between two calls in the same cell, as well as between adjacent cells.
The xe2x80x98cellsxe2x80x99 from which these cellular telephone networks get their name are the coverage areas of the individual fixed radio base stations (FIG. 2). The problem facing the network operator is to allocate channels to base stations such that demand for channels across the network is met, while keeping interference within acceptable levels. These aims are clearly in conflict: the more channels allocated to each base station the harder it is to plan the channel reuse to avoid unacceptable interference.
An added difficulty is that the demand across the network is neither uniform nor static. Some cells will experience high demand at particular times of the day but lower than average demand for the rest of the day, for example cells containing major arteries of commuter traffic. Even worse, for efficient channel allocation, are the unpredictable fluctuations in demand resulting from events such as road accidents.
It is currently common practice for operators to use a fixed channel allocation plan. The channels used by any particular base station are determined by a xe2x80x9cfrequency planxe2x80x9d. This plan is only modified every few months if necessary to meet quality of service criteria, for example to meet changes in demand, and to allow for the installation of new base stations. During the existence of one frequency plan, each base station has its own allocation of channels, which remains the same throughout the life of the plan.
New base station technology, allowing speedy changes in channel use by base stations, is making the idea of dynamic channel allocation planning more attractive (Akaiwa, Y. and Andoh, H.: Channel Segregation-A Self-Organized Dynamic Channel Allocation Method: Application To TDMA/FDMA Microcellular System. IEEE Journal On Selected Areas In Communications 11 (6) (1993) 949-954).
Dynamic planning takes two forms: xe2x80x98offlinexe2x80x99 in which the channel use is planned to vary through the day according to the expected fluctuations in demand, and xe2x80x98onlinexe2x80x99 in which the channel use is reallocated in response to changes in demand as they happen. Dynamic planning can allow quality of service to be maintained as demand rises without the need for costly base station construction (Delli Priscoli, F., Magnani, N. P., Palestini, V. and Sestini, F.: Application Of Dynamic Channel Allocation To The GSM Cellular Network. IEEE Journal On Selected Areas In Communications 15 (8) (1997) 1558-1566). xe2x80x98Onlinexe2x80x99 dynamic planning is particularly attractive because it allows the network to deal with the unexpected as it happens, where an offline plan may fail. However, online planning requires operation in real time, and is thus more demanding of processing power.
Producing an efficient channel allocation plan is not only an important part of running an efficient mobile network, it is a formidable abstract mathematical problem. If there are k available channels the number of different ways of allocating l channels to a cell is:       (                  k        !                              (                                    (                              k                -                l                            )                        !                    )                ⁢                  (                      l            !                    )                      )    .
For a network of j cells with l available channels there are therefore       (                  k        !                              (                                    (                              k                -                l                            )                        !                    )                ⁢                  (                      l            !                    )                      )    j
ways of allocating l channels to each cell. For example in the network of FIG. 2A, with fifty-eight cells, there are (29!/(25! 4!))58=(23751)58=6xc3x9710253 different ways of assigning, to each cell, four of the twenty-nine available channels. Clearly an exhaustive search of solution space is not an appropriate method for optimising such a problem. Various processes have been applied to this problem including:
xe2x80x98subspace approachxe2x80x99 (Lochtie, G. D. and Mehler, M. J.: Subspace Approach To Channel Assignment In Mobile Communications. IEE Proceedings Communications 142 (3) (1995) 179-185),
xe2x80x9csimulated annealingxe2x80x9d (Aarts, E. and Korst, J.: Simulated Annealing and Boltzmann Machines. Wiley (1989) and
xe2x80x9cneural networksxe2x80x9d (Kunz, D.: Channel Assignment For Cellular Radio Using Neural Networks. IEEE Transactions on Vehicular Technology 40 (1) (1991) 188-193).
Lochtie, G. D., van Eiji, C. A. and Mehler, M. J. compare various methods in Comparison Of Energy Minimising Processs For Channel Assignment In Mobile Radio Networks: Proceedings of the 8th IEEE International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC""97) 3 (1997) 786-790)).
According to the present invention a channel allocation process is provided in which the process starts from a position of homogeneity in which all cells have the potential to use all channels, and develops ever greater heterogeneities which move it towards a solution by processing a combination of short and medium range interactions among the cells themselves, causing each cell (i.e. each base station) of the cellular telephone network to inhibit its neighbours from using a given channel, to generate a usage factor for each channel in each cell indicative of the level of interference to be expected on that channel in that cell. This process may be carried out by a single processor emulating the network, which can, if the system is to be carried out in real time (dynamically), then transmit the results of the process to each base station, or it can be carried out by the individual base stations, each interacting with its neighbours.
The process arrives at progressively better solutions by a process of mutual inhibition between cells. No global information is available to these cells and each must act on the basis of the inhibition it perceives from its neighbours. The process does not search solution space but instead moves through shades of grey towards a black and white solution (FIG. 2).
Further aspects of the invention relate to a cellular telephone system having means for performing this process, and to a computer program product directly loadable into the internal memory of a digital computer, said program product comprising software code portions for performing the process when said product is run on a computer, either to control a real network or as a planning tool.
The invention also extends to a computer-usable carrier carrying computer-readable program means for performing the various steps of the process. The computer-readable program means may be embodied on any suitable carrier readable by a suitable computer input device, such as CD-ROM, optically readable marks, magnetic media, punched card, or on an electromagnetic or optical signal.